{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Value of the Rearranged Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重排数字的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>num</code> 。<strong>重排</strong> <code>num</code> 中的各位数字，使其值 <strong>最小化</strong> 且不含 <strong>任何</strong> 前导零。</p>\n",
    "\n",
    "<p>返回不含前导零且值最小的重排数字。</p>\n",
    "\n",
    "<p>注意，重排各位数字后，<code>num</code> 的符号不会改变。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = 310\n",
    "<strong>输出：</strong>103\n",
    "<strong>解释：</strong>310 中各位数字的可行排列有：013、031、103、130、301、310 。\n",
    "不含任何前导零且值最小的重排数字是 103 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>num = -7605\n",
    "<strong>输出：</strong>-7650\n",
    "<strong>解释：</strong>-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。\n",
    "不含任何前导零且值最小的重排数字是 -7650 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-10<sup>15</sup> &lt;= num &lt;= 10<sup>15</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-value-of-the-rearranged-number](https://leetcode.cn/problems/smallest-value-of-the-rearranged-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-value-of-the-rearranged-number](https://leetcode.cn/problems/smallest-value-of-the-rearranged-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['310', '-7605']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "\n",
    "        res = \"\"\n",
    "        hs = defaultdict(int)\n",
    "\n",
    "        for p in range(9, 1, -1):\n",
    "            while n != 1 and n % p == 0:\n",
    "                n //= p\n",
    "                hs[p] += 1\n",
    "\n",
    "            if n == 1:\n",
    "                for i in range(2, 10):\n",
    "                    str_i = str(i)\n",
    "                    while hs[i] != 0:\n",
    "                        res += str_i\n",
    "                        hs[i] -= 1\n",
    "                return res\n",
    "\n",
    "        return \"-1\"    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "\n",
    "        res = \"\"\n",
    "\n",
    "        for p in range(9, 1, -1):\n",
    "            str_p = str(p)\n",
    "            while n != 1 and n % p == 0:\n",
    "                n //= p\n",
    "                res = str_p + res\n",
    "\n",
    "            if n == 1:\n",
    "                return res\n",
    "\n",
    "        return \"-1\"    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        while n != 1:\n",
    "            for num in range(9, 1, -1):\n",
    "                if n % num == 0:\n",
    "                    ans.append(num)\n",
    "                    n //= num \n",
    "                    break\n",
    "            else:\n",
    "                return \"-1\"\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n==1:return \"1\"\n",
    "        k=9\n",
    "        res=[]\n",
    "        while k>1:\n",
    "            while n%k==0:\n",
    "                res.append(str(k))\n",
    "                n//=k\n",
    "            k-=1\n",
    "        if n!=1:return \"-1\"\n",
    "        res.reverse()\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        # 其实就是分解质因数，分解成个位数相乘\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        while n != 1:\n",
    "            for num in range(9, 1, -1):\n",
    "                if n % num == 0:\n",
    "                    ans.append(num)\n",
    "                    n //= num \n",
    "                    break\n",
    "            else:\n",
    "                return \"-1\"\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    如果你是一个质数，并没有1到9的\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        # if n == 1:\n",
    "        #     return '1'\n",
    "        # @cache\n",
    "        # def helper(num: int) -> str:\n",
    "        #     if num == 1:\n",
    "        #         return ''\n",
    "        #     if num < 10:\n",
    "        #         return str(num)\n",
    "        #     for i in range(2, 10):\n",
    "        #         if num % i == 0:\n",
    "        #             if helper(num // i) != '-1':\n",
    "        #                 return str(i) + helper(num // i)\n",
    "        #             else:\n",
    "        #                 return '-1'\n",
    "        #     else:\n",
    "        #         return '-1'\n",
    "        # return helper(n)\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        return ''.join(str(i) * cnt[i] for i in range(2, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        ans = ''.join(str(i) * cnt[i] for i in range(2, 10))\n",
    "        return ans if ans else '1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        ans=[]\n",
    "        if n==1:\n",
    "            return \"1\"\n",
    "        for i in range(9,1,-1):\n",
    "            while n%i==0:\n",
    "                n=n//i\n",
    "                ans.append(i)\n",
    "        if n!=1:\n",
    "            return \"-1\"\n",
    "        return \"\".join(map(str,sorted(ans)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心 + 因数分解\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "\n",
    "        lis = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "        cnt = Counter()\n",
    "        ans = ''\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans = str(i) + ans\n",
    "        return ans if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        list = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                list.append(i)\n",
    "        return \"\".join(str(i) for i in list[::-1]) if n == 1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "\n",
    "        cnts = [0] * 10\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i \n",
    "                cnts[i]+=1\n",
    "            if n == 1:\n",
    "                break \n",
    "        else:\n",
    "            return \"-1\"\n",
    "\n",
    "        return \"\".join([str(i) * cnts[i] for i in range(2,10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        res = \"\"\n",
    "        for p in range(9,1,-1):\n",
    "            while n%p==0:\n",
    "                res+=str(p)\n",
    "                n//=p\n",
    "        return res[::-1] if n==1 else \"-1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        ans = []\n",
    "        for i in range(9,1,-1):\n",
    "            if n == 1:\n",
    "                break\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans.append(str(i))\n",
    "        return ''.join(ans)[::-1] if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        ans = ''\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        for i in range(9, 1, -1):\n",
    "            if n == 1:\n",
    "                break\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                ans += str(i)\n",
    "        if ans == '':\n",
    "            return '-1'\n",
    "        return ans[::-1] if n == 1 else '-1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                cnt[i] += 1\n",
    "        if n > 1:\n",
    "            return \"-1\"\n",
    "        ans = \"\".join(str(i) * cnt[i] for i in range(2, 10))\n",
    "        return ans if ans else \"1\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        ans = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                ans.append(str(i))\n",
    "                n //= i\n",
    "        return \"-1\" if n > 10 else \"\".join(ans)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        res = []\n",
    "        for d in range(9, 1, -1):\n",
    "            while n % d == 0:\n",
    "                n //= d\n",
    "                res.append(str(d))\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        else:\n",
    "            return ''.join(reversed(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        counter = defaultdict(int)\n",
    "        for f in [2, 3, 5, 7]:\n",
    "            while n % f == 0:\n",
    "                n //= f\n",
    "                counter[f] += 1\n",
    "\n",
    "        if n > 1:\n",
    "            return \"-1\"\n",
    "\n",
    "        while counter[3] >= 2:\n",
    "            counter[3] -= 2\n",
    "            counter[9] += 1\n",
    "        while counter[2] >= 3:\n",
    "            counter[2] -= 3\n",
    "            counter[8] += 1\n",
    "        while counter[2] >= 1 and counter[3] >= 1:\n",
    "            counter[2] -= 1\n",
    "            counter[3] -= 1\n",
    "            counter[6] += 1\n",
    "        while counter[2] >= 2:\n",
    "            counter[2] -= 2\n",
    "            counter[4] += 1\n",
    "\n",
    "        return \"\".join(str(k) * v for k, v in sorted(counter.items()))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        ans = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while n % i == 0:\n",
    "                ans.append(i)\n",
    "                n //= i\n",
    "        if n != 1:\n",
    "            return '-1'\n",
    "        ans.sort()\n",
    "        return ''.join(map(str, ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        cnt = [0] * 10\n",
    "        primes = [7, 5, 3, 2]\n",
    "        for p in primes:\n",
    "            while n % p == 0:\n",
    "                cnt[p] += 1\n",
    "                n //= p\n",
    "        if n > 1:\n",
    "            return '-1'\n",
    "        ans = '9' * (cnt[3] // 2) + '8' * (cnt[2] // 3) + '7' * cnt[7]\n",
    "        cnt[3] %= 2\n",
    "        cnt[2] %= 3\n",
    "        if cnt[3] and cnt[2]:\n",
    "            ans = ans + '6'\n",
    "            cnt[3] -= 1\n",
    "            cnt[2] -= 1\n",
    "        if cnt[5] > 0:\n",
    "            ans = ans + '5' * cnt[5]\n",
    "        if cnt[2] == 2:\n",
    "            ans = ans + '4'\n",
    "            cnt[2] -= 2\n",
    "        if cnt[3] == 1:\n",
    "            ans = ans + '3'\n",
    "        if cnt[2] == 1:\n",
    "            ans = ans + '2'\n",
    "        return ans[::-1] if ans else '1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        lis = []\n",
    "        for i in range(9,1,-1):\n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "                lis.append(i)\n",
    "            if n == 1: break\n",
    "        return \"\".join(str(i) for i in lis[::-1]) if n == 1 else \"-1\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        sb = []\n",
    "        for p in range(9, 1, -1):\n",
    "            while n % p == 0:\n",
    "                sb.append(str(p))\n",
    "                n //= p\n",
    "        if n != 1:\n",
    "            return \"-1\"\n",
    "        return \"\".join(sb[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        def f(x, s):\n",
    "            if x < 10:\n",
    "                return s+str(x)\n",
    "            for i in range(9, 1, -1):\n",
    "                if x % i == 0:\n",
    "                    r = f(x//i, s+str(i))\n",
    "                    if r != '-1':\n",
    "                        return r\n",
    "            return '-1'\n",
    "        s = f(n, '')  \n",
    "        if s == '-1':\n",
    "            return s\n",
    "        r = ''\n",
    "        i = len(s)-1\n",
    "        while i >= 0:\n",
    "            if i-1 >= 0:\n",
    "                if int(s[i]) * int(s[i-1]) < 10:\n",
    "                    r += str(int(s[i]) * int(s[i-1]))\n",
    "                    i -= 2\n",
    "                else:\n",
    "                    r += s[i]\n",
    "                    i -= 1\n",
    "            else:\n",
    "                r += s[i]\n",
    "                i -= 1\n",
    "        return r\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n < 10:\n",
    "            return str(n)\n",
    "        ans = []\n",
    "        while n > 1:\n",
    "            ok = False\n",
    "            for i in range(9, 1, -1):\n",
    "                if n % i == 0:\n",
    "                    ans.append(i)\n",
    "                    n //= i\n",
    "                    ok = True\n",
    "                    break\n",
    "            if not ok :\n",
    "                break\n",
    "        if n > 10: return \"-1\"\n",
    "        ans.sort()\n",
    "        return \"\".join(map(str, ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        cnt = [0]*8\n",
    "        for p in [2,3,5,7]:\n",
    "            while n%p==0:\n",
    "                n//=p\n",
    "                cnt[p]+=1\n",
    "        if n>1: return \"-1\"\n",
    "\n",
    "        @cache\n",
    "        def insert(cur,nxt):\n",
    "            for j in range(len(cur)):\n",
    "                if cur[j]>nxt:\n",
    "                    return cur[:j]+nxt+cur[j:]\n",
    "            return cur+nxt\n",
    "\n",
    "        dp = [[\"-1\" for j in range(cnt[3]+1)] for i in range(cnt[2]+1)]\n",
    "        dp[0][0]=\"\"\n",
    "\n",
    "        for cnt2 in range(cnt[2]+1):\n",
    "            for cnt3 in range(cnt[3]+1):\n",
    "                possible = [[\"2\",1,0],[\"4\",2,0],[\"8\",3,0],[\"3\",0,1],[\"9\",0,2],[\"6\",1,1]]\n",
    "                mn = 64\n",
    "                for nxt,cnt2n,cnt3n in possible:\n",
    "                    if cnt2>=cnt2n and cnt3>=cnt3n:\n",
    "                        temp = insert(dp[cnt2-cnt2n][cnt3-cnt3n],nxt)\n",
    "                        if dp[cnt2][cnt3]==\"-1\" or len(temp)<mn or (len(temp)==mn and temp<dp[cnt2][cnt3]):\n",
    "                            mn = len(temp)\n",
    "                            dp[cnt2][cnt3]=temp\n",
    "\n",
    "        return \"\".join(sorted(\"5\"*cnt[5]+\"7\"*cnt[7]+dp[-1][-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "@cache\n",
    "def get_prime_factors(n: int) -> list:\n",
    "    factors, i = [], 2\n",
    "    while i ** 2 <= n:\n",
    "        if i >= 10 and n >= 10: return []\n",
    "        if n % i: i += 1\n",
    "        else:\n",
    "            n //= i\n",
    "            factors.append(i)\n",
    "    if n > 1: factors.append(n)\n",
    "    return factors\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        if n == 1: return \"1\"\n",
    "        factors = get_prime_factors(n) # 包含重复元素\n",
    "        \n",
    "        if not factors: return \"-1\"\n",
    "        if max(factors) >= 10: return \"-1\"\n",
    "        cnts = Counter(factors)\n",
    "        cnts[8], cnts[2] = divmod(cnts[2], 3)\n",
    "        cnts[9], cnts[3] = divmod(cnts[3], 2)\n",
    "        if cnts[2] and cnts[3]:\n",
    "            cnts[6] += 1\n",
    "            cnts[2] -= 1\n",
    "            cnts[3] -= 1\n",
    "        if cnts[2] == 2: \n",
    "            cnts[4] += 1\n",
    "            cnts[2] = 0\n",
    "        ans = \"\"\n",
    "        for k in sorted(cnts.keys()):\n",
    "            ans += str(k) * cnts[k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "\n",
    "        if n==1: return \"1\"\n",
    "        cnt = [0]*8\n",
    "        for p in [2,3,5,7]:\n",
    "            while n%p==0:\n",
    "                n//=p\n",
    "                cnt[p]+=1\n",
    "        if n>1: return \"-1\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(cnt2,cnt3):\n",
    "            if cnt2+cnt3==0: return \"\"\n",
    "            mn = 64\n",
    "            possible = [[\"2\",1,0],[\"4\",2,0],[\"8\",3,0],[\"3\",0,1],[\"9\",0,2],[\"6\",1,1]]\n",
    "            res = \"\"\n",
    "            for nxt,cnt2n,cnt3n in possible:\n",
    "                if cnt2>=cnt2n and cnt3>=cnt3n:\n",
    "                    temp = nxt+dfs(cnt2-cnt2n,cnt3-cnt3n)\n",
    "                    if len(temp)<mn or (len(temp)==mn and \"\".join(sorted(temp))<\"\".join(sorted(res))):\n",
    "                        mn = len(temp)\n",
    "                        res = temp            \n",
    "            return res\n",
    "\n",
    "        return \"\".join(sorted(\"5\"*cnt[5]+\"7\"*cnt[7]+dfs(cnt[2],cnt[3])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def smallestNumber(self, n: int) -> str:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        if n in [4,6,8,9]:\n",
    "            return str(n)\n",
    "\n",
    "        def prime_factorization(n):\n",
    "            i = 2\n",
    "            factors = []\n",
    "            while i * i <= n:\n",
    "                if n % i:\n",
    "                    i += 1\n",
    "                    if i > 9:\n",
    "                        return \"-1\"\n",
    "                else:\n",
    "                    n //= i\n",
    "                    factors.append(i)\n",
    "            if n > 1:\n",
    "                if n > 9:\n",
    "                    return \"-1\"\n",
    "                factors.append(n)\n",
    "            return factors\n",
    "\n",
    "        ll = prime_factorization(n)\n",
    "        \n",
    "        if ll == \"-1\":\n",
    "            return ll\n",
    "\n",
    "        for i in ll:\n",
    "            if i > 9:\n",
    "                return '-1'\n",
    "        m1 = defaultdict(int)\n",
    "        for i in ll:\n",
    "            m1[i] += 1\n",
    "        v3 = m1.get(3, 0)\n",
    "        gap1 = v3 // 2\n",
    "        m1[3] -= gap1 * 2\n",
    "        m1[9] += gap1\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        gap2 = v2 // 3\n",
    "        m1[2] -= gap2 * 3\n",
    "        m1[8] += gap2\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        v3 = m1.get(3, 0)\n",
    "        gap2 = min(v2, v3)\n",
    "        m1[2] -= gap2\n",
    "        m1[3] -= gap2\n",
    "        m1[6] += gap2\n",
    "\n",
    "        v2 = m1.get(2, 0)\n",
    "        gap2 = v2 // 2\n",
    "        m1[2] -= gap2 * 2\n",
    "        m1[4] += gap2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        xx = []\n",
    "        for i in m1:\n",
    "            for j in range(m1[i]):\n",
    "                xx.append(i)\n",
    "        xx.sort()\n",
    "        return ''.join([str(i) for i in xx])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num >= 0:\n",
    "            c = Counter(str(num))\n",
    "            ans = ''\n",
    "            for i in '123456789':\n",
    "                if c[i]:\n",
    "                    ans += i\n",
    "                    c[i] -= 1\n",
    "                    break\n",
    "            for i in '0123456789':\n",
    "                ans += i * c[i]\n",
    "        else:\n",
    "            c = Counter(str(-num))\n",
    "            ans = ''\n",
    "            for i in '9876543210':\n",
    "                ans += i * c[i]\n",
    "            ans = '-' + ans\n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num>0:\n",
    "            str_num=str(num)\n",
    "            lst=[int(i) for i in str_num]\n",
    "            lst.sort()\n",
    "            if(lst[0]==0):\n",
    "                lst1=list(filter(lambda x:x!=0,lst))\n",
    "                m=min(lst1)\n",
    "                idx=lst.index(m)\n",
    "                lst[0]=m\n",
    "                lst[idx]=0\n",
    "            result=''\n",
    "            for i in lst:\n",
    "                result=result+str(i)\n",
    "            return int(result)\n",
    "        if num<0:\n",
    "            str_num=str(num)\n",
    "            lst=[int(i) for i in str_num[1:]]\n",
    "            lst.sort()\n",
    "            lst=lst[::-1]\n",
    "            result=''\n",
    "            for i in lst:\n",
    "                result=result+str(i)\n",
    "            return -int(result)\n",
    "        if num==0:\n",
    "            return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num // 10 == 0:\n",
    "            return num\n",
    "        string = str(num)\n",
    "        if string[0] == \"-\":\n",
    "            tmp = list(map(int, string[1:]))\n",
    "            tmp.sort(reverse=True)\n",
    "            tmp = list(map(str, tmp))\n",
    "            tmp = \"\".join(tmp)\n",
    "            tmp = -int(tmp)\n",
    "            return tmp\n",
    "        else:\n",
    "            tmp = list(map(int, string))\n",
    "            tmp.sort()\n",
    "            k = 0\n",
    "            while k< len(tmp) and not tmp[k] :\n",
    "                k += 1\n",
    "            tmp[k], tmp[0] = tmp[0], tmp[k]\n",
    "            tmp = list(map(str, tmp))\n",
    "            tmp = \"\".join(tmp)\n",
    "            tmp = int(tmp)\n",
    "            return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        if num < 0:\n",
    "            sgn = -1\n",
    "            num = abs(num)\n",
    "            digits = sorted(int(digit) for digit in str(num))[::-1]\n",
    "            return int(\"\".join(str(digit) for digit in digits)) * -1\n",
    "        else:\n",
    "            digits = sorted(int(digit) for digit in str(num))\n",
    "            i = 0\n",
    "            while digits[i] == 0:\n",
    "                i += 1\n",
    "            digits[0], digits[i] = digits[i], digits[0]\n",
    "            return int(\"\".join(str(digit) for digit in digits))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        \n",
    "\n",
    "        if num<0:\n",
    "            str_num = str(abs(num))\n",
    "            temp = sorted(str_num,reverse=True)\n",
    "            return int(\"-\"+\"\".join(temp))\n",
    "        str_num = str(num)\n",
    "        temp = sorted(str_num)\n",
    "        n = len(temp)\n",
    "        if n<=1:\n",
    "            return num\n",
    "        if temp[0]!='0':\n",
    "            return int(\"\".join(temp))\n",
    "        for i in range(n):\n",
    "            if temp[i]!='0':\n",
    "                temp[i],temp[0] = temp[0],temp[i]\n",
    "                \n",
    "                return int(\"\".join(temp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if not num:\n",
    "            return num\n",
    "        \n",
    "        flag = True if num < 0 else False\n",
    "        num = -num if flag else num\n",
    "\n",
    "        record = []\n",
    "        while num:\n",
    "            tmp = num % 10\n",
    "            record.append(-tmp if flag else tmp)\n",
    "            num = num // 10\n",
    "\n",
    "        record = sorted(record)\n",
    "\n",
    "        index, pre = 0, 0\n",
    "        for i, data in enumerate(record):\n",
    "            if data:\n",
    "                index = i\n",
    "                pre = data\n",
    "                break\n",
    "\n",
    "        record.pop(index)\n",
    "\n",
    "        res = pre\n",
    "        for n in record:\n",
    "            res = res * 10 + n\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num >= 0:\n",
    "            nums = []\n",
    "            while num >= 1:\n",
    "                h = num%10\n",
    "                nums.append(h)\n",
    "                num = num // 10\n",
    "            nums.sort()\n",
    "            res = 0\n",
    "            cnt = 0\n",
    "            n = len(nums)\n",
    "            for i in range(n):\n",
    "                if nums[i] == 0:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    res += nums[i]\n",
    "                    break\n",
    "            for i in range(cnt):\n",
    "                res*= 10\n",
    "            for i in range(cnt+1,n):\n",
    "                res *= 10\n",
    "                res += nums[i]\n",
    "            return res\n",
    "        else:\n",
    "            num = -num\n",
    "            nums = []\n",
    "            while num >= 1:\n",
    "                h = num%10\n",
    "                nums.append(h)\n",
    "                num = num // 10\n",
    "            nums.sort(reverse = True)\n",
    "            n = len(nums)\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                res*= 10\n",
    "                res += nums[i]\n",
    "            return -res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        negative = (num) < 0\n",
    "        num = abs(num)\n",
    "        digits = sorted(int(digit) for digit in str(num))\n",
    "        \n",
    "        if negative:\n",
    "            digits = digits[::-1]\n",
    "        else:\n",
    "            if digits[0] == 0:\n",
    "                i = 1\n",
    "                while digits[i] == 0:\n",
    "                    i += 1\n",
    "                digits[0], digits[i] = digits[i], digits[0]\n",
    "\n",
    "        ans = int(\"\".join(str(digit) for digit in digits))\n",
    "        return -ans if negative else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num>0:\n",
    "            SignF = True\n",
    "        elif num<0:\n",
    "            SignF = False\n",
    "            num = -1*num\n",
    "        else:\n",
    "            return 0\n",
    "        listn = list(str(num))\n",
    "        heapq.heapify(listn)\n",
    "        ans = ''\n",
    "        ztemp=''\n",
    "        for i in range(len(listn)):\n",
    "            x = heapq.heappop(listn)\n",
    "            if SignF:\n",
    "                if x == '0':\n",
    "                    ztemp = ztemp + x\n",
    "                else:\n",
    "                    ans = ans + x\n",
    "            else:\n",
    "                ans = x + ans\n",
    "        if SignF and len(ztemp)!=0:\n",
    "            ans = ans[0] + ztemp + ans[1:]\n",
    "\n",
    "        if SignF:\n",
    "            ans = int(ans)\n",
    "        else:\n",
    "            ans = -1*int(ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        arr = []\n",
    "        if num < 0:\n",
    "            num *= -1\n",
    "            while num:\n",
    "                arr.append(num%10)\n",
    "                num //= 10\n",
    "            ans = 0\n",
    "            for i in sorted(arr, reverse = True):\n",
    "                ans = ans * 10 + i\n",
    "            return -ans\n",
    "        else:\n",
    "            zeros = []\n",
    "            while num:\n",
    "                if num % 10 == 0:\n",
    "                    zeros.append(0)\n",
    "                else:\n",
    "                    arr.append(num%10)\n",
    "                num //= 10\n",
    "            ans = 0\n",
    "            arr.sort()\n",
    "            ans += arr[0]\n",
    "            arr = arr[1:]\n",
    "            arr = zeros + arr\n",
    "            for i in arr:\n",
    "                ans *= 10\n",
    "                ans += i\n",
    "            return ans            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return num\n",
    "        str_num = str(num)\n",
    "        l_list = []\n",
    "        if num > 0:\n",
    "            for i in str_num:\n",
    "                l_list.append(i)\n",
    "            l_list.sort()\n",
    "            if l_list[0] != '0':\n",
    "                return int(''.join(l_list))\n",
    "            else:\n",
    "                for i in range(len(l_list)):\n",
    "                    if l_list[i] != '0':\n",
    "                        break\n",
    "                tmp = l_list.pop(i)\n",
    "                l_list = [tmp] + l_list\n",
    "                return int(''.join(l_list))\n",
    "        if num < 0:\n",
    "            for i in str_num[1:]:\n",
    "                l_list.append(i)\n",
    "            l_list.sort(reverse = True)\n",
    "            l_list = ['-'] + l_list\n",
    "            return int(''.join(l_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if not num:\n",
    "            return 0\n",
    "        if num > 0:\n",
    "            lst = list(str(num)) \n",
    "            lst.sort()\n",
    "            for i in range(len(lst)):\n",
    "                if lst[i] == '0':\n",
    "                    continue\n",
    "                lst[0], lst[i] = lst[i], lst[0]\n",
    "                break\n",
    "            return int(''.join(lst))\n",
    "        lst = list(str(num)[1:]) \n",
    "        lst.sort(reverse = True)\n",
    "        return int('-'+''.join(lst))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        neg = num < 0\n",
    "        num = abs(num)\n",
    "        s = list(str(num))\n",
    "        if neg:\n",
    "            return -int(''.join(sorted(s, reverse=True)))\n",
    "        s.sort()\n",
    "        if s[0] == '0':\n",
    "            for i in range(1, len(s)):\n",
    "                if s[i] != '0':\n",
    "                    s[0], s[i] = s[i], s[0]\n",
    "                    break\n",
    "        ans = int(''.join(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num > 0:\n",
    "            lst = sorted(str(num))\n",
    "            c = min(set(lst) - {'0'})\n",
    "            lst.remove(c)\n",
    "            return int(''.join([c] + lst))\n",
    "        else:\n",
    "            return - int(''.join(sorted(str(- num), reverse = True)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        dp = [0] * 10\n",
    "        if num > 0:\n",
    "            for c in str(num):\n",
    "                dp[int(c)] += 1\n",
    "            ans = \"\"\n",
    "            for i in range(1,10):\n",
    "                if dp[i]:\n",
    "                    ans += str(i)\n",
    "                    dp[i] -= 1\n",
    "                    break\n",
    "            for i in range(10):\n",
    "                ans += str(i) * dp[i]\n",
    "            return int(ans)\n",
    "        else:\n",
    "            for c in str(num)[1:]:\n",
    "                dp[int(c)] += 1\n",
    "                ans = \"-\"\n",
    "                for i in range(9,-1,-1):\n",
    "                    ans += str(i) * dp[i]\n",
    "            return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        cnt = [0] * 10\n",
    "        n = abs(num)\n",
    "        while n:\n",
    "            cnt[n % 10] += 1\n",
    "            n //= 10\n",
    "        # print(f'{cnt}')\n",
    "        if num > 0:\n",
    "            for i in range(10):\n",
    "                if cnt[i] and i > 0:\n",
    "                    ans = i\n",
    "                    cnt[i] -= 1\n",
    "                    for j in range(10):\n",
    "                        while cnt[j] > 0:\n",
    "                            ans = ans * 10 + j\n",
    "                            cnt[j] -= 1\n",
    "                    return ans\n",
    "        else:\n",
    "            ans = 0\n",
    "            for i in range(9,-1,-1):\n",
    "                while cnt[i]:\n",
    "                    # print(f'i={i}')\n",
    "                    ans = ans * 10 + i\n",
    "                    cnt[i] -= 1\n",
    "            return -ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        num_list = []\n",
    "        if num > 0:\n",
    "            while num > 0:\n",
    "                num_list.append( num%10 )\n",
    "                num //= 10\n",
    "            num_list.sort()\n",
    "            for i in num_list:\n",
    "                if i > 0:\n",
    "                    res = i\n",
    "                    num_list.remove(i)\n",
    "                    break\n",
    "            for i in num_list:\n",
    "                res *= 10\n",
    "                res += i\n",
    "        elif num <0:\n",
    "            num = num*-1\n",
    "            while num > 0:\n",
    "                num_list.append( num%10 )\n",
    "                num //= 10\n",
    "            num_list.sort(reverse=True )\n",
    "            res = 0\n",
    "            for i in num_list:\n",
    "                res *= 10\n",
    "                res += i\n",
    "            res *= -1\n",
    "        else:\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        s = str(abs(num))\n",
    "        if num < 0:\n",
    "            return -int(''.join(sorted(s, reverse=True)))\n",
    "        start = min(c for c in s if c != '0')\n",
    "        l = list(s)\n",
    "        l[l.index(start)] = ''\n",
    "        l.sort()\n",
    "        l[0] = start\n",
    "        return int(''.join(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "\n",
    "        num = list(str(num))\n",
    "        if num[0] == \"-\":\n",
    "            num = num[1:]\n",
    "            num.sort(reverse=True)\n",
    "            return int(\"-\" + ''.join(num))\n",
    "        else:\n",
    "            num.sort()\n",
    "            i = 0 \n",
    "            while num[i] == '0':\n",
    "                i += 1\n",
    "            num[i], num[0] = num[0], num[i]\n",
    "            return int(''.join(num))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num>0:\n",
    "            num = sorted(list(str(num)))\n",
    "            if num[0] == '0':\n",
    "                i = 1\n",
    "                while i <len(num):\n",
    "                    if num[i] !='0':\n",
    "                        tem = num[i]\n",
    "                        num[i] = '0'\n",
    "                        num[0] = tem\n",
    "                        break\n",
    "                    i+=1\n",
    "                    \n",
    "            return int(''.join(num))\n",
    "        else:\n",
    "            num = sorted(list(str(0-num)),reverse = True)\n",
    "            return 0-int(''.join(num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        seq,n=sorted([x for x in str(num) if x not in ('0','-')]),str(num).count('0')\n",
    "        return int(seq[0]+'0'*n+''.join(seq[1:])) if num>0 else -int(''.join(seq[::-1])+'0'*n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        negative = (num) < 0\n",
    "        num = abs(num)\n",
    "        digits = sorted(int(digit) for digit in str(num))\n",
    "        \n",
    "        if negative:\n",
    "            digits = digits[::-1]\n",
    "        else:\n",
    "            if digits[0] == 0:\n",
    "                i = 1\n",
    "                while digits[i] == 0:\n",
    "                    i += 1\n",
    "                digits[0], digits[i] = digits[i], digits[0]\n",
    "\n",
    "        ans = int(\"\".join(str(digit) for digit in digits))\n",
    "        return -ans if negative else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        flag = num > 0\n",
    "        s = str(abs(num))\n",
    "        n = len(s)\n",
    "        zero_list = []\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            if s[i] == \"0\":\n",
    "                zero_list.append(s[i])\n",
    "            else:\n",
    "                nums.append(s[i])\n",
    "        ans = None\n",
    "        nums.sort()\n",
    "        if flag:\n",
    "            ans = nums[0] + \"\".join(zero_list) + \"\".join(nums[1:])\n",
    "        else:\n",
    "            ans = \"-\" + \"\".join(nums[::-1]) + \"\".join(zero_list)\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            return -1 * int(\"\".join(sorted(str(num)[1:], reverse=True)))\n",
    "        num = list(str(num))\n",
    "        num.sort()\n",
    "        for i in range(len(num)):\n",
    "            if num[i] != \"0\":\n",
    "                num[i], num[0] = num[0], num[i]\n",
    "                break\n",
    "        \n",
    "        return int(\"\".join(num))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        snum=str(num)\n",
    "        if num<0:\n",
    "            return -int(''.join(sorted(list(snum[1:]))[::-1]))\n",
    "        else:\n",
    "            rl=sorted(list(snum))\n",
    "            i=0\n",
    "            while rl[i]=='0':\n",
    "                i+=1\n",
    "            rl[0],rl[i]=rl[i],rl[0]\n",
    "            return int(''.join(rl))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num<=0:\n",
    "            temp=str(-num)\n",
    "            res=list(c for c in temp)\n",
    "            res.sort(reverse=True)\n",
    "            return int(\"-\"+\"\".join(c for c in res))\n",
    "        else:\n",
    "            temp=str(num)\n",
    "            res=list(c for c in temp)\n",
    "            res.sort()\n",
    "            for i in range(len(res)):\n",
    "                if res[i]=='0':\n",
    "                    continue\n",
    "                return int(res[i]+\"0\"*i+\"\".join(res[i+1:]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getResByNum(self, n, k):\n",
    "        res = 0\n",
    "        for i in range(0, k):\n",
    "            res = res * 10 + n\n",
    "        return res\n",
    "\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        tmp = 0\n",
    "        if num > 0:\n",
    "            tmp = 1\n",
    "        else:\n",
    "            tmp = -1\n",
    "            num *= tmp\n",
    "        nums = [0] * 10\n",
    "        zeroCnt = 0\n",
    "        while (num > 0):\n",
    "            temp = num % 10\n",
    "            nums[temp] += 1\n",
    "            num = num // 10\n",
    "        res = 0\n",
    "        if tmp > 0:\n",
    "            for i in range(1, 10):\n",
    "                if nums[i] == 0:\n",
    "                    continue\n",
    "                if res == 0:\n",
    "                    res += i * math.pow(10, nums[0])\n",
    "                    nums[i] -= 1\n",
    "                res = res * math.pow(10, nums[i]) + self.getResByNum(i, nums[i])\n",
    "        else:\n",
    "            for i in range(9, 0, -1):\n",
    "                if nums[i] == 0:\n",
    "                    continue\n",
    "                res = res * math.pow(10, nums[i]) + self.getResByNum(i, nums[i])\n",
    "            res = res * math.pow(10, nums[0])\n",
    "        return int(tmp * res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        positive = 1\n",
    "        if num < 0:\n",
    "            positive = 0\n",
    "            num = -num\n",
    "        cnt = [0] * 10\n",
    "        while num:\n",
    "            cnt[num % 10] += 1\n",
    "            num //= 10\n",
    "        if positive:\n",
    "            rgn_first = list(range(1, 10))\n",
    "            rgn = list(range(10))\n",
    "        else:\n",
    "            rgn_first = list(range(9, 0, -1))\n",
    "            rgn = list(range(9, -1, -1))\n",
    "        ret = 0\n",
    "        for i in rgn_first:\n",
    "            if cnt[i]:\n",
    "                ret = i\n",
    "                cnt[i] -= 1\n",
    "                break\n",
    "        for i in rgn:\n",
    "            while cnt[i]:\n",
    "                cnt[i] -= 1\n",
    "                ret = ret * 10 + i\n",
    "        return ret if positive else -ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if not num:\n",
    "            return 0\n",
    "        if num > 0:\n",
    "            lst = list(str(num)) \n",
    "            lst.sort()\n",
    "            for i in range(len(lst)):\n",
    "                if lst[i] == '0':\n",
    "                    continue\n",
    "                lst[0], lst[i] = lst[i], lst[0]\n",
    "                break\n",
    "            return int(''.join(lst))\n",
    "        lst = list(str(num)[1:]) \n",
    "        lst.sort(reverse = True)\n",
    "        return int('-'+''.join(lst))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        elif num > 0:\n",
    "            nums = sorted([int(c) for c in str(num)])\n",
    "            for i, x in enumerate(nums):\n",
    "                if x != 0:\n",
    "                    break\n",
    "            nums = [nums.pop(i)] + nums\n",
    "            return int(''.join([str(x) for x in nums]))\n",
    "        else:\n",
    "            num = abs(num)\n",
    "            nums = sorted([int(c) for c in str(num)], reverse=True)\n",
    "            return -int(''.join([str(x) for x in nums]))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSmasllest(self, ls:list, neg:bool) -> int:\n",
    "        ans = \"\"\n",
    "        if neg:\n",
    "            ls.sort(reverse=True)\n",
    "        else:\n",
    "            ls.sort()\n",
    "        i = 0\n",
    "        while i<len(ls) and ls[i]=='0':\n",
    "            i += 1\n",
    "        first = ls.pop(i)\n",
    "        first += ''.join(ls)\n",
    "        ans += first\n",
    "        return int(ans) if not neg else -int(ans)\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        sn = str(num)\n",
    "        flag = False\n",
    "        if sn[0]=='-':\n",
    "            flag = True\n",
    "            sn = sn[1:]\n",
    "        return self.getSmasllest(list(sn),True) if flag else self.getSmasllest(list(sn),False)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        s = str(num)\n",
    "        if s[0] != \"-\":\n",
    "            lst = sorted(list(s))\n",
    "            for i in range(len(lst)):\n",
    "                if lst[i] != '0':\n",
    "                    lst[i], lst[0] = lst[0], lst[i]\n",
    "                    break\n",
    "            return int(\"\".join(lst))\n",
    "        lst = sorted(list(s[1:]), reverse=True)\n",
    "        return int(\"\".join(lst))*(-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        a = 1\n",
    "        if num < 0:\n",
    "            a = 0\n",
    "            num = - num\n",
    "        hh = []\n",
    "        while num != 0:\n",
    "            hh.append(num % 10)\n",
    "            num //= 10\n",
    "        hh.sort()\n",
    "        res = 0\n",
    "        if a > 0:\n",
    "            if hh[0] == 0:\n",
    "                for i in range(len(hh)):\n",
    "                    if hh[i] != 0:\n",
    "                        hh[0] = hh[i]\n",
    "                        hh[i] = 0\n",
    "                        break\n",
    "            for i in hh:\n",
    "                res = res * 10 + i\n",
    "        else:\n",
    "            for i in hh[::-1]:\n",
    "                res = res * 10 + i\n",
    "            return -res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        ans = ''\n",
    "        if num > 0:\n",
    "            num = sorted(str(num))\n",
    "        elif num < 0:\n",
    "            num = sorted(str(num)[1:], reverse = True)\n",
    "            num = ['-'] + num\n",
    "        else:\n",
    "            return 0\n",
    "        zeros = ''\n",
    "        first_num = 1\n",
    "        for i in range(len(num)):\n",
    "            if (num[i] == '0') and (first_num == 1):\n",
    "                zeros += num[i]\n",
    "            else:\n",
    "                if first_num == 1:\n",
    "                    ans += num[i]\n",
    "                    ans += zeros\n",
    "                    first_num = 0\n",
    "                else:\n",
    "                    ans += num[i]\n",
    "        return int(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        def getMin(cnt):\n",
    "            ans = \"\"\n",
    "            for i in range(10):\n",
    "                if i != 0 and cnt[i] > 0:\n",
    "                    ans += str(i)\n",
    "                    cnt[i] -= 1\n",
    "                    break\n",
    "            \n",
    "            for i in range(10):\n",
    "                if cnt[i] > 0:\n",
    "                    ans += str(i) * cnt[i]\n",
    "            return ans\n",
    "        \n",
    "        def getMax(s):\n",
    "            ans = \"\"\n",
    "            for i in range(9, -1, -1):                \n",
    "                if cnt[i] > 0:\n",
    "                    ans += str(i) * cnt[i]\n",
    "            return ans\n",
    "        \n",
    "        def str2Num(s):\n",
    "            ans = 0\n",
    "            for x in s:\n",
    "                ans = ans * 10 + ord(x) - ord('0')\n",
    "            return ans\n",
    "        \n",
    "        cnt = [0] * 10\n",
    "        n = abs(num)\n",
    "        while n:\n",
    "            cnt[n % 10] += 1\n",
    "            n //= 10\n",
    "        \n",
    "        s = getMin(cnt) if num > 0 else getMax(cnt)\n",
    "        \n",
    "        if num > 0:\n",
    "            return str2Num(s) \n",
    "        else:\n",
    "            return -str2Num(s)\n",
    "        \n",
    "        \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        opera = -1\n",
    "        if num > 0:\n",
    "            opera = 1\n",
    "        hash_ = [0] * 10\n",
    "        for c in str(num):\n",
    "            if c == '-':\n",
    "                continue\n",
    "            hash_[ord(c) - ord('0')] += 1\n",
    "        print(hash_)\n",
    "        res = ''\n",
    "        if opera == 1:\n",
    "            for i in range(1, 10):\n",
    "                if hash_[i] != 0:\n",
    "                    if len(res) == 0:\n",
    "                        res += str(i)\n",
    "                        hash_[i] -= 1\n",
    "                        while hash_[0]:\n",
    "                            res += '0'\n",
    "                            hash_[0] -= 1\n",
    "                        while hash_[i]:\n",
    "                            res += str(i)\n",
    "                            hash_[i] -= 1\n",
    "                    else:\n",
    "                        while hash_[i]:\n",
    "                            res += str(i)\n",
    "                            hash_[i] -= 1\n",
    "            return int(res)\n",
    "        else:\n",
    "            for i in range(9, -1, -1):\n",
    "                while hash_[i]:\n",
    "                    res += str(i)\n",
    "                    hash_[i] -= 1\n",
    "            return int('-' + res)\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:return 0\n",
    "        if num < 0:\n",
    "            st = 1\n",
    "        else:st = 0\n",
    "        if not st:\n",
    "            C = Counter(str(num))\n",
    "            for i in range(1,10):\n",
    "                if C[str(i)]:\n",
    "                    C[str(i)] -= 1\n",
    "                    res = str(i)\n",
    "                    break\n",
    "            for i in range(10):\n",
    "                if C[str(i)]:\n",
    "                    res += str(i) * C[str(i)]\n",
    "            return int(res)\n",
    "        else:\n",
    "            C = Counter(str(num)[1:])\n",
    "            res = ''\n",
    "            for i in range(9,-1,-1):\n",
    "                if C[str(i)]:\n",
    "                    res += str(i) * C[str(i)]\n",
    "            return int('-' + res)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        if num>0:\n",
    "            res=[0]*10\n",
    "            while num>0:\n",
    "                res[num%10]+=1\n",
    "                num//=10\n",
    "            ans=[]\n",
    "            for i in range(1,10):\n",
    "                if res[i]!=0:\n",
    "                    ans.append(str(i))\n",
    "                    res[i]-=1\n",
    "                    break\n",
    "            for i in range(10):\n",
    "                ans.append(str(i)*res[i])\n",
    "            return int(\"\".join(ans))\n",
    "        if num<0:\n",
    "            num=-num\n",
    "            res=[0]*10\n",
    "            while num>0:\n",
    "                res[num%10]+=1\n",
    "                num//=10\n",
    "            ans=[]\n",
    "            for i in range(9,-1,-1):\n",
    "                ans.append(str(i)*res[i])\n",
    "            return -1*int(\"\".join(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitNum(self, num):\n",
    "        nums= []\n",
    "        while num > 0:\n",
    "            nums.append(num % 10)\n",
    "            num = num // 10\n",
    "        return nums\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "\n",
    "        nums = self.splitNum(abs(num))\n",
    "        if num > 0:\n",
    "            nums.sort()\n",
    "            for i, n in enumerate(nums):\n",
    "                if n != 0:\n",
    "                    nums[0], nums[i] = n, nums[0]\n",
    "                    break\n",
    "            pn = 1\n",
    "        else:\n",
    "            nums.sort(key=lambda x: -x)\n",
    "            pn = -1\n",
    "        res = 0\n",
    "        for n in nums:\n",
    "            res = res * 10 + n\n",
    "        \n",
    "        return pn * res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        ans, n = 0, 0\n",
    "        if num == 0:\n",
    "            return num\n",
    "        nums = []\n",
    "        flag = -1 if num < 0 else 1\n",
    "        if flag == -1:\n",
    "            num = -num\n",
    "        while num:\n",
    "            insert_num = num % 10\n",
    "            num //= 10\n",
    "            i = n - 1\n",
    "            nums.append(insert_num)\n",
    "            while i >= 0:\n",
    "                if insert_num > nums[i]:\n",
    "                    nums[i + 1] = insert_num\n",
    "                    break\n",
    "                else:\n",
    "                    nums[i + 1] = nums[i]\n",
    "                    nums[i] = insert_num\n",
    "                i -= 1\n",
    "            n += 1\n",
    "\n",
    "        if flag == -1:\n",
    "            nums = nums[::-1]\n",
    "\n",
    "        i = 0\n",
    "        while nums[i] == 0:\n",
    "            i += 1\n",
    "        if i != 0:\n",
    "            nums[0] = nums[i]\n",
    "            nums[i] = 0\n",
    "            i = 0\n",
    "        while i < n:\n",
    "            ans *= 10\n",
    "            ans += nums[i]\n",
    "            i += 1\n",
    "        return ans * flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        flag = False\n",
    "        if num < 0:\n",
    "            num = -num\n",
    "            flag = True\n",
    "        res = list(str(num))\n",
    "        if flag:\n",
    "            res.sort(reverse=True)\n",
    "            res = \"\".join(res)\n",
    "            return -int(res)\n",
    "        else:\n",
    "            res.sort()\n",
    "            i = 0\n",
    "            while i < len(res) and res[i] == \"0\":\n",
    "                i += 1\n",
    "            res = [res[i]] + res[0: i] + res[i + 1: ]\n",
    "            res = \"\".join(res)\n",
    "            return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestNumber(self, num: int) -> int:\n",
    "        返回 = sorted(list(str(num)))\n",
    "        if 返回[0] == \"-\":\n",
    "            return -int(\"\".join(返回[1:][::-1]))\n",
    "        for i in range(1, len(返回)):\n",
    "            if 返回[i] != \"0\" and 返回[i-1] == \"0\":\n",
    "                返回[0] = 返回[i]\n",
    "                返回[i] = \"0\"\n",
    "                break\n",
    "        return int(\"\".join(返回))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
